package com.arron.algorithm.leetcodetop100.回溯;

import com.arron.algorithm.tree.TreeNode;
import com.sun.org.apache.bcel.internal.generic.GETFIELD;

import java.util.ArrayList;
import java.util.List;

/**
 * 95. 不同的二叉搜索树 II
 */
public class 不同的二叉搜索树II {



    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> ans = new ArrayList<TreeNode>();
        if (n == 0) {
            return ans;
        }
        return generateTrees(1, n);
    }

    public List<TreeNode> generateTrees(int start,int end){

        List<TreeNode> treeNodes=new ArrayList<>();
        if (start>end){
            treeNodes.add(null);
            return treeNodes;
        }

        for (int i = start; i <=end ; i++) {
            List<TreeNode> leftTreeNodes = generateTrees(start, i - 1);
            List<TreeNode> rightTreeNodes = generateTrees(i+1, end);


            for (TreeNode leftTreeNode : leftTreeNodes) {
                for (TreeNode rightTreeNode : rightTreeNodes) {
                        TreeNode root =  new TreeNode(i);
                        root.left = leftTreeNode;
                        root.right = rightTreeNode;
                    treeNodes.add(root);
                }
            }
        }

        return treeNodes;

    }

    public static void main(String[] args) {
        不同的二叉搜索树II generateTrees = new 不同的二叉搜索树II();
        generateTrees.generateTrees(3);

    }


}
